// 思路：利用kmp得到字符串的next数组，可以得到最长相等前后缀
// 用该字符串匹配目标字符串时，如果发现不匹配，跳到上一个最长相等前后缀长度位置
// 时间复杂度：O(n)，n是字符串的长度
// 空间复杂度：O(n)，next数组的大小

function getNext(str) {
    let left = 0
    let right = 1
    let next = new Array(str.length).fill(0)
    while (right < str.length) {
        while (left > 0 && str[left] !== str[right]) {
            left = next[left - 1]
        }
        if (str[left] === str[right]) {
            left++
        }
        next[right] = left
        right++
    }
    return next
}

function strStr(haystack, needle) {
    if (!needle) {
        return 0
    }
    let next = getNext(needle)
    let j = 0
    for (let i = 0; i < haystack.length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1]
        }
        if (haystack[i] === needle[j]) {
            j++
        }
        if (j >= needle.length) {
            return i - needle.length + 1
        }
    }
    return 0
}

console.log(strStr('aabaabaafa', 'aabaaf'))